package com.muchfish.algorithm.queue;

import java.util.NoSuchElementException;

/**
 * 基于链表实现队列
 * 跟栈一样，队列可以用数组来实现，也可以用链表来实现。<br>
 * 用数组实现的栈叫作顺序栈，用链表实现的栈叫作链式栈。<br>
 * 同样，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。<br>
 * <img src="../../../../../image/PixPin_2025-01-02_14-57-03.png"><br>
 * @param <E>
 */
public class LinkedListQueue<E> implements Queue<E> {

    int size;
    Node<E> head;
    Node<E> tail;

    public LinkedListQueue() {
    }


    @Override
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    @Override
    public boolean offer(E e) {
        linkLast(e);
        return true;
    }

    @Override
    public E remove() {
        if (size == 0) {
            throw new NoSuchElementException("队列为空!");
        }
        Node<E> h = unlinkHead();
        return h.val;
    }

    @Override
    public E poll() {
        if (size == 0) {
            return null;
        }
        Node<E> h = unlinkHead();
        return h.val;
    }

    @Override
    public E element() {
        if (size == 0) {
            throw new NoSuchElementException("队列为空!");
        }
        Node<E> h = head;
        return h.val;
    }

    @Override
    public E peek() {
        if (size == 0) {
            return null;
        }
        Node<E> h = head;
        return h.val;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return false;
    }

    private void linkLast(E e) {
        Node<E> t = tail;
        Node<E> newNode = new Node<>(e, null);
        tail = newNode;
        if (t == null) {
            head = newNode;
        } else {
            t.next = newNode;
        }
        size++;
    }

    private Node<E> unlinkHead(){
        Node<E> h = head;
        head = h.next;
        h.next = null;
        size--;
        return h;
    }



    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node<E> h = head;
        while (h!=null){
            sb.append(h.val).append("->");
            h = h.next;
        }
        return sb.append("null").toString();
    }


    public static void main(String[] args) {
        Queue<String> queue = new LinkedListQueue<>();
        queue.add("黑马程序员");
        queue.offer("博学谷");
        queue.offer("传智汇");
        queue.offer("传智专修学院");
        System.out.println("队列是否为空："+queue.isEmpty()+",队列元素个数为："+queue.size());
        System.out.println(queue);
        System.out.println("队列头元素:"+queue.remove());
        System.out.println(queue);
        System.out.println("队列头元素:"+queue.poll());
        System.out.println(queue);
        System.out.println("队列头元素:"+queue.element());
        System.out.println(queue);
        System.out.println("队列头元素:"+queue.peek());
        System.out.println(queue);
    }

    private static class Node<E> {
        E val;
        Node<E> next;

        public Node(E val, Node<E> next) {
            this.val = val;
            this.next = next;
        }
    }
}
